#include "splay.h"
#include <stdlib.h>
#include "fatal.h"

struct SplayNode {
	ElementType Element;
	SplayTree Left;
	SplayTree Right;
};

typedef struct SplayNode *Position;
static Position NullNode = NULL; /* Needs initialization */

SplayTree Initialize(void) {
	if (NullNode == NULL) {
		NullNode = malloc(sizeof(struct SplayNode));
		if (NullNode == NULL)
			FatalError("Out of space!!!");
		NullNode->Left = NullNode->Right = NullNode;
	}
	return NullNode;
}

static SplayTree Splay(ElementType Item, Position X);

SplayTree MakeEmpty(SplayTree T) {
	if (T != NullNode) {
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		free(T);
	}
	return NullNode;
}

void PrintTree(SplayTree T) {
	if (T != NullNode) {
		PrintTree(T->Left);
		printf("%d ", T->Element);
		PrintTree(T->Right);
	}
}

SplayTree Find(ElementType X, SplayTree T) {
	return Splay(X, T);
}

SplayTree FindMin(SplayTree T) {
	return Splay( NegInfinity, T);
}

SplayTree FindMax(SplayTree T) {
	return Splay( Infinity, T);
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static Position SingleRotateWithLeft(Position K2) {
	Position K1;

	K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	return K1; /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static Position SingleRotateWithRight(Position K1) {
	Position K2;

	K2 = K1->Right;
	K1->Right = K2->Left;
	K2->Left = K1;

	return K2; /* New root */
}

/* START: fig12_6.txt */
/* Top-down splay procedure, */
/* not requiring Item to be in tree */

SplayTree Splay(ElementType Item, Position X) {
	static struct SplayNode Header;
	Position LeftTreeMax, RightTreeMin;

	Header.Left = Header.Right = NullNode;
	LeftTreeMax = RightTreeMin = &Header;
	NullNode->Element = Item;

	while (Item != X->Element) {
		if (Item < X->Element) {
			if (Item < X->Left->Element)
				X = SingleRotateWithLeft(X);
			if (X->Left == NullNode)
				break;
			/* Link right */
			RightTreeMin->Left = X;
			RightTreeMin = X;
			X = X->Left;
		} else {
			if (Item > X->Right->Element)
				X = SingleRotateWithRight(X);
			if (X->Right == NullNode)
				break;
			/* Link left */
			LeftTreeMax->Right = X;
			LeftTreeMax = X;
			X = X->Right;
		}
	} /* while Item != X->Element */

	/* Reassemble */
	LeftTreeMax->Right = X->Left;
	RightTreeMin->Left = X->Right;
	X->Left = Header.Right;
	X->Right = Header.Left;

	return X;
}
/* END */

/* START: fig12_7.txt */
SplayTree Insert(ElementType Item, SplayTree T) {
	static Position NewNode = NULL;

	if (NewNode == NULL) {
		NewNode = malloc(sizeof(struct SplayNode));
		if (NewNode == NULL)
			FatalError("Out of space!!!");
	}
	NewNode->Element = Item;

	if (T == NullNode) {
		NewNode->Left = NewNode->Right = NullNode;
		T = NewNode;
	} else {
		T = Splay(Item, T);
		if (Item < T->Element) {
			NewNode->Left = T->Left;
			NewNode->Right = T;
			T->Left = NullNode;
			T = NewNode;
		} else if (T->Element < Item) {
			NewNode->Right = T->Right;
			NewNode->Left = T;
			T->Right = NullNode;
			T = NewNode;
		} else
			return T; /* Already in the tree */
	}

	NewNode = NULL; /* So next insert will call malloc */
	return T;
}
/* END */

/* START: fig12_8.txt */
SplayTree Remove(ElementType Item, SplayTree T) {
	Position NewTree;

	if (T != NullNode) {
		T = Splay(Item, T);
		if (Item == T->Element) {
			/* Found it! */
			if (T->Left == NullNode)
				NewTree = T->Right;
			else {
				NewTree = T->Left;
				NewTree = Splay(Item, NewTree);
				NewTree->Right = T->Right;
			}
			free(T);
			T = NewTree;
		}
	}

	return T;
}

/* END */

ElementType Retrieve(SplayTree T) {
	return T->Element;
}
